package com.shuo.dsa.test;


import com.shuo.dsa.model.TreeNode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * Created by shuoGG on 2018/9/27 0027
 */
public class TreeUtil {
    public static void main(String[] args) {
        bfs(createTree(20));
    }

    public static TreeNode createTree() {
        TreeNode treeNode1 = new TreeNode(1);
        TreeNode treeNode2 = new TreeNode(2);
        TreeNode treeNode3 = new TreeNode(3);
        TreeNode treeNode4 = new TreeNode(4);
        TreeNode treeNode5 = new TreeNode(5);
        TreeNode treeNode6 = new TreeNode(6);
        TreeNode treeNode7 = new TreeNode(7);
        TreeNode treeNode8 = new TreeNode(8);
        TreeNode treeNode9 = new TreeNode(9);
        treeNode1.left = treeNode2;
        treeNode1.right = treeNode3;
        treeNode2.left = treeNode4;
        treeNode2.right = treeNode5;
        treeNode3.left = treeNode6;
        treeNode3.right = treeNode7;
        treeNode4.left = treeNode8;
        treeNode4.right = treeNode9;
        return treeNode1;
    }

    public static TreeNode createTree(int n) {
        List<TreeNode> list = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            list.add(new TreeNode(i + 1));
        }
        for (int i = 0; i < n; i++) {
            TreeNode cur = list.get(i);
            int leftIndex = (i + 1) * 2 - 1;
            if ((leftIndex) > list.size() - 1) break;
            cur.left = list.get(leftIndex);
            if ((leftIndex + 1) > list.size() - 1) break;
            cur.right = list.get(leftIndex + 1);
        }
        return list.get(0);
    }

    public static void bfs(TreeNode node) {
        List<List<Integer>> ret = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(node);
        while (!queue.isEmpty()) {
            List<Integer> layerNodes = new ArrayList<>();
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode a = queue.poll();
                layerNodes.add(a.value);
                if (a.left != null)
                    queue.offer(a.left);
                if (a.right != null)
                    queue.offer(a.right);
            }
            ret.add(layerNodes);
        }
        /* 遍历出树的图形 */
        printTree(ret);
    }

    private static void printTree(List<List<Integer>> layerList) {
        int s = layerList.size();
        for (int i = 0; i < layerList.size(); i++) {
            List<Integer> integerList = layerList.get(i);
            for (Integer integer : integerList) {
                System.out.print(spaces(power2(s - i)) + integer + spaces(power2(s - i)));
            }
            System.out.println();
        }
    }

    private static void printTreePretty(List<List<Integer>> layerList) {
        int s = layerList.size();
        for (int i = 0; i < layerList.size(); i++) {
            List<Integer> integerList = layerList.get(i);
            for (Integer integer : integerList) {
                System.out.print(spaces(power2(s - i)) + integer + spaces(power2(s - i)));
            }
            System.out.println();
        }
    }

    public static String spaces(int n) {
        StringBuilder t = new StringBuilder();
        for (int i = 0; i < n; i++) {
            t.append(" ");
        }
        return t.toString();
    }

    public static int power2(int n) {
        if (n == 0)
            return 1;
        int value = 1;
        for (int i = 0; i < n; i++) {
            value *= 2;
        }
        return value;
    }
}
